Міністерство освіти і науки України Національний університет “Львівська політехніка” кафедра прикладної математики КУРСОВА РОБОТА з курсу дискретна математика на тему: „Автомати з магазинною пам’яттю. Контекстно-вільні граматики”  ЗМІСТ Вступ. Основні поняття теорії формальних мов і граматик............................................................................................................3 Означення МП-автомата……………………………………………………………….3 Варіанти МП-автоматів………………………………………………………………..6 Еквівалентність МП-автоматів і КВ-граматик……………………………………...10 Детерміновані МП-автомати…………………………………………………………16 Синтез МП-автомата………………………………….................................................21 Програмна реалізація синтезу ДМП-автомата……………………………………...23 Список використаної літератури…………………….................................................27 Основні поняття теорії формальних мов і граматик. Для того, щоб зрозуміти теорію алгоритмічних мов, необхідно оперувати найпростішими, але найфундаментальнішими поняттями теорії формальних мов і граматик, мати чітку уяву про ієрархію мови – літера, слово, мова. Отже, літера – це простий неподільний знак. Множина літер утворює алфавіт. Ланцюжок (слово, стрічка) – це впорядкована скінченна послідовність літер алфавіту. ε–порожній ланцюжок, ланцюжок нульової довжини. Над ланцюжками допускаються операції конкатенації (об’єднання ланцюжків) та обертання стрічок. Мовою LA, породженою алфавітом А, називається сукупність всіх стрічок, отриманих у даній мові. Дамо також означення граматики. Формальною породжуючою граматикою G називається четвірка <N,Т,Р,S> , де Т – скінченна не порожня множина символів, яка називається термінальним або основним словником граматики G; N – скінченна не порожня множина символів, що називається нетермінальним (допоміжним) словником граматики G, причому Т
N=Ø, Т
N=V –об’єднаний словник граматики G; S – початковий символ або аксіома граматики G, S – нетермінал і є головною метою граматики G; Р – скінченна множина правил граматики G, елемент цієї множини можна задати у вигляді пари (α , β); ця пара – правило виводу або правило підстановки і часто записується у вигляді α→β. Варто зауважити, що α,β
{N
Т}* (A*– множина всіх можливих ланцюжків над алфавітом А, A*=А0
А1
А2
...
Аn
... і називається замиканням алфавіту А або повною ітерацією; є ще неповна ітерація:А+ = A* \{ε}). Правила підстановки називають також схемою граматики. Означимо відношення
G (відношення в граматиці G, надалі писатимемо без позначки внизу, коли розумітимемо про яку граматику йдеться) на множині (N
T)* так: якщо αβγ – стрічка з (N
T)* і β → δ – правило з Р, то αβγ
αδγ. Транзитивне замикання відношення
позначають через
+ (φ
+ ψ читається: ψ виводима з φ нетривіальним чином), а його рефлексивне і транзитивне замикання:
* (φ
* ψ читається: ψ виводима з φ). Існує чотири класи мов і граматик за Хомським, але ми користуватимемося класом, що містить так звані контексно-вільні мови (КВ-мови). Це – мови, що породжуються граматиками, які мають правила виводу такого виду: α→β, де α
N, β
V+, тобто ліві частини правил виводу мають лише один нетермінальний символ. Означення МП-автомата Автомат з магазинною пам’яттю—розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомат з магазинною пам’яттю—односторонній недетермінований розпізнавач , в потенційно нескінченній пам’яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожний момент доступний тільки верхній елемент магазина. Розпізнавач такого типу зображений на рисунку 1. А1 А2  Аn  Вхідна стрічка (тільки читати) Z1  Z2    Zm   Магазин Рис.1.Автомат з магазинною пам’ят...